package com.mypaper.schedule;

import com.mypaper.elem.LinkedListNode;
import com.mypaper.elem.PairElement;
import com.mypaper.elem.ScheduleElement;
import com.mypaper.elem.ScheduleNode;
import com.mypaper.elem.TaskNode;
import com.mypaper.list.IdleList;
import com.mypaper.list.ListPriority;
import com.mypaper.list.OrderLinkedList;
import com.mypaper.list.ScheduleResults;


public class HCPFDSchedule extends ScheduleAlgorithm{
	public short[][] MIIP;
	float[][] EST;
	float[][] EFT;
	float[][] DEST;
	float[][] DEFT;
	float[][] DAT;
	float[][] readyTime;
	boolean[][] isScheduled;
	
	public HCPFDSchedule(short vertexNum, short procNum)
	{
		scheduleResults=new ScheduleResults();
		reliedDup=new short[vertexNum];//每个任务依赖的duplication任务编号
		MIIP=new short[vertexNum][procNum];//每个任务在处理器上的MIIP
		AST=new float[vertexNum];//每个任务在遍历所有处理器后计算出的实际开始执行时间
		AFT=new float[vertexNum];//每个任务在遍历所有处理器后计算出的实际结束执行时间
		idleTimeList=new IdleList[procNum];//每个处理器一个空闲时间块列
		for(int i=0; i<procNum; i++){
			idleTimeList[i]=new IdleList();
			idleTimeList[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
		EST=new float[vertexNum][procNum];//每个任务在遍历每个处理器时计算出的最早开始执行时间
		EFT=new float[vertexNum][procNum];//每个任务在遍历每个处理器时计算出的最早结束执行时间
		DEST=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate MIIP计算出的最早开始执行时间
		DEFT=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate MIIP计算出的最早结束执行时间
		MEST=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate时MIIP计算出的最早开始执行时间
		MEFT=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate时MIIP计算出的最早结束执行时间
		DAT=new float[vertexNum][procNum];
		readyTime=new float[vertexNum][procNum];
		isScheduled=new boolean[vertexNum][procNum];
		assiProc2Task=new short[vertexNum];
	}
	
	public void HCPFD_Algorithm(short vertexNum, short procNum, ListPriority prior, 
			float[][] vertexWeight, float[][] edgeWeight)
	{
		int i,j;			
		
		for(i=0;i<vertexNum;i++){
			reliedDup[i]=-1;
			assiProc2Task[i]=-1;
		}
		
		isScheduled=new boolean[vertexNum][procNum];
		
		int currTaskIndex=-1;
		
		for(i=0; i<vertexNum; i++){
			AST[i]=Float.MAX_VALUE;
			AFT[i]=Float.MAX_VALUE;
			for(j=0; j<procNum; j++){		
				EST[i][j]=Float.MAX_VALUE;
				EFT[i][j]=Float.MAX_VALUE;
				DEFT[i][j]=Float.MAX_VALUE;
				DEST[i][j]=Float.MAX_VALUE;
				isScheduled[i][j]=false;
				MIIP[i][j]=-1;
				DAT[i][j]=0;
				readyTime[i][j]=0;
			}
		}
		
		float EFT_back=Float.MAX_VALUE;
		
		PairElement searchItem=new PairElement(), beFoundItem=new PairElement();
	
		OrderLinkedList[] idleTimeListBack=new OrderLinkedList[procNum];
		OrderLinkedList idleTimeListBackDup=new OrderLinkedList();
		idleTimeListBackDup.insertNode(new PairElement(0,Float.MAX_VALUE));
		
		for(i=0; i<procNum; i++){
			idleTimeListBack[i]=new OrderLinkedList();
			idleTimeListBack[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
		
		TaskNode currentTask=prior.first;
		
		while(currentTask!=null){
			currTaskIndex=currentTask.info.index;
			//System.out.println("currTask: "+currTaskIndex);
			for(short k=0; k<procNum; k++){
				for(short l=0; l<vertexNum; l++){//求所有父节点在当前处理器上的到达时间及当前任务的MIIP
					if(edgeWeight[l][currTaskIndex]!=0){
						if(assiProc2Task[l]==k)//对于每个父节点，求到达处理器的时间
							DAT[l][k]=AFT[l];
						else{
							DAT[l][k]=AFT[l]+edgeWeight[l][currTaskIndex];
						}
						if(readyTime[currTaskIndex][k]<DAT[l][k]){//找MIIP父节点及其到达时间
							readyTime[currTaskIndex][k]=DAT[l][k];
							MIIP[currTaskIndex][k]=l;
						}
					}	
				}
				idleTimeListBack[k].copyList(idleTimeList[k]);
				LinkedListNode currentIdle=idleTimeListBack[k].first;
				boolean found=false;
				while(currentIdle!=null&&!found){
					searchItem.setNum(readyTime[currTaskIndex][k],readyTime[currTaskIndex][k]+vertexWeight[currTaskIndex][k]);
					//要为searchItem找合适的空闲时间
					beFoundItem=(PairElement)idleTimeList[k].search(searchItem);//beFoundItem为找到的空闲时间段
					//System.out.print(beFoundItem);
					if(beFoundItem!=null)
						found=true;
					currentIdle=currentIdle.next;
				}
				if(found==true){
					EST[currTaskIndex][k]=Math.max(readyTime[currTaskIndex][k], beFoundItem.start);
					EFT[currTaskIndex][k]=EST[currTaskIndex][k]+vertexWeight[currTaskIndex][k];
					idleTimeListBack[k].deleteNode(beFoundItem);
					if(searchItem.start>beFoundItem.start){
						idleTimeListBack[k].insertNode(new PairElement(beFoundItem.start,EST[currTaskIndex][k]));
						idleTimeListBack[k].insertNode(new PairElement(EFT[currTaskIndex][k],beFoundItem.end));
					}else{
						idleTimeListBack[k].insertNode(new PairElement(EFT[currTaskIndex][k],beFoundItem.end));
					}	
				}
				
				if(EFT_back>EFT[currTaskIndex][k]){
					EFT_back=EFT[currTaskIndex][k];
					assiProc2Task[currTaskIndex]=k;
				}	
			}
				
			///////////////////////////////////////
			//下面判断duplication情况下是否减小EFT
			int currProc=assiProc2Task[currTaskIndex];//记录当前任务分配的处理器
			int miip=MIIP[currTaskIndex][currProc];//记录当前任务的MIIP;
			idleTimeListBackDup.copyList(idleTimeList[currProc]);
			boolean foundD=false, found2=false;
			float RT;
			PairElement searchDup=new PairElement(), beFoundDup=new PairElement();
			LinkedListNode currentIdle=idleTimeListBackDup.first;//处理器K上第一个空闲块
			if(miip!=-1&&isScheduled[miip][currProc]==false)
			{//MIIP存在并且MIIP未在k上执行
				RT=readyTime[miip][currProc];//MIIP的所需数据到达k的时间
				foundD=false;
				while(currentIdle!=null&&!foundD){
					searchDup.setNum(RT, RT+vertexWeight[miip][currProc]);
					beFoundDup=(PairElement)idleTimeListBackDup.search(searchDup);
					if(beFoundDup!=null)
						foundD=true;
					currentIdle=currentIdle.next;
				}
				if(foundD==true){//找到可供复制的空闲时间，计算MIIP的结束时间及currentTask的开始结束时间
					MEST[miip][currProc]=Math.max(RT, beFoundDup.start);
					MEFT[miip][currProc]=MEST[miip][currProc]+vertexWeight[miip][currProc];	
					idleTimeListBackDup.deleteNode(beFoundDup);
					if(searchDup.start>beFoundDup.start){
						idleTimeListBackDup.insertNode(new PairElement(beFoundDup.start,MEST[miip][currProc]));
						idleTimeListBackDup.insertNode(new PairElement(MEFT[miip][currProc],beFoundDup.end));
					}else{
						idleTimeListBackDup.insertNode(new PairElement(MEFT[miip][currProc],beFoundDup.end));
					}
					
					float readyTimeBack=MEFT[miip][currProc];

					if(readyTimeBack<EST[currTaskIndex][currProc])
					{//如果duplication task结束提前
						
						for(int l=0; l<vertexNum; l++){//求所有父节点在当前处理器上的到达时间及当前任务的MIIP
							if(edgeWeight[l][currTaskIndex]!=0){						
								if(l!=miip && readyTimeBack<DAT[l][currProc]){//找MIIP父节点及其到达时间
									readyTimeBack=DAT[l][currProc];
								}
							}	
						}
						
						float startT=readyTimeBack;
						float endT=readyTimeBack+vertexWeight[currTaskIndex][currProc];
						
						found2=false;
						currentIdle=idleTimeListBackDup.first;
						while(currentIdle!=null&&!found2){
							searchItem.setNum(startT, endT);
							//要为searchItem找合适的空闲时间						
							//beFoundItem[k].makeCopy((PairElement)idleTimeListBackDup[k].search(searchItem[k]));//beFoundItem为找到的空闲时间段
							beFoundItem=(PairElement)idleTimeListBackDup.search(searchItem);//beFoundItem为找到的空闲时间段
							if(beFoundItem!=null)
								found2=true;
							currentIdle=currentIdle.next;
						}
						if(found2==true){//更新空闲时间链表
							DEST[currTaskIndex][currProc]=Math.max(searchItem.start, beFoundItem.start);
							DEFT[currTaskIndex][currProc]=DEST[currTaskIndex][currProc]+vertexWeight[currTaskIndex][currProc];	
							idleTimeListBackDup.deleteNode(beFoundItem);
							if(searchItem.start>beFoundItem.start){
								idleTimeListBackDup.insertNode(new PairElement(beFoundItem.start,DEST[currTaskIndex][currProc]));
								idleTimeListBackDup.insertNode(new PairElement(DEFT[currTaskIndex][currProc],beFoundItem.end));
							}else{
								idleTimeListBackDup.insertNode(new PairElement(DEFT[currTaskIndex][currProc],beFoundItem.end));
							}
						}
					}
				}
			}
			
			if(EFT_back>DEFT[currTaskIndex][currProc])
				AFT[currTaskIndex]=DEFT[currTaskIndex][currProc];
			else 
				AFT[currTaskIndex]=EFT_back;
			AST[currTaskIndex]=AFT[currTaskIndex]-vertexWeight[currTaskIndex][currProc];
			
			ScheduleElement perTask=new ScheduleElement();
			if(EFT_back>DEFT[currTaskIndex][currProc]){	
				isScheduled[MIIP[currTaskIndex][currProc]][currProc]=true;
				perTask.setNum(MIIP[currTaskIndex][currProc],currProc,
						MEST[MIIP[currTaskIndex][currProc]][currProc],
						MEFT[MIIP[currTaskIndex][currProc]][currProc]);
				scheduleResults.insertNode(perTask);
				reliedDup[currTaskIndex]=MIIP[currTaskIndex][currProc];
				idleTimeList[currProc].copyList(idleTimeListBackDup);
				//scheduleResults.print();
				//System.out.println();
			}
			else{
				idleTimeList[currProc].copyList(idleTimeListBack[currProc]);
			}	
			
			isScheduled[currTaskIndex][currProc]=true;
			perTask.setNum(currTaskIndex,currProc,AST[currTaskIndex],AFT[currTaskIndex]);
			scheduleResults.insertNode(perTask);
			EFT_back=Float.MAX_VALUE;
			//scheduleResults.print();
			//System.out.println();
			currentTask=currentTask.next;
			}	
		scheduleResults.print();
		//System.out.println();
		//dag.prior.print();
	}
	
	public float energyCal(int procNum){
		float enerSum=0;
        float timeSum=0;	
        float totalTime=0;
        float power=(float)0.925, idlePower=(float)0.260;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			ScheduleElement perTask=currentTask.info;
			if(flag[perTask.processorID]!=true)
				flag[perTask.processorID]=true;
			if(perTask.endTime>procTermTime[perTask.processorID])
				procTermTime[perTask.processorID]=perTask.endTime;
			timeSum+=(perTask.endTime-perTask.startTime);
			currentTask=currentTask.next;
		}
		
		for(int i=0; i<procNum; i++){
			System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		System.out.println("idletime： "+(totalTime-timeSum));
		System.out.println("busytime： "+timeSum);
		enerSum=timeSum*power+(totalTime-timeSum)*idlePower;
		return enerSum;
	}
	
	
	
	public float makespan(){
		float curr=0;
		ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			if(curr<currentTask.info.endTime)
				curr=currentTask.info.endTime;
			currentTask=currentTask.next;
		}
		return curr;
	}
	
	public float timeCal(int procNum){
        float timeSum=0;	
        float totalTime=0;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			ScheduleElement perTask=currentTask.info;
			if(flag[perTask.processorID]!=true)
				flag[perTask.processorID]=true;
			if(perTask.endTime>procTermTime[perTask.processorID])
				procTermTime[perTask.processorID]=perTask.endTime;
			timeSum+=(perTask.endTime-perTask.startTime);
			currentTask=currentTask.next;
		}
		
		for(int i=0; i<procNum; i++){
			//System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		//System.out.println("idletime： "+(totalTime-timeSum));
		System.out.println("busytime： "+timeSum);
		System.out.println();
		return timeSum;
	}
}
